package leetcode.D400.T313;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-03-15 10:58:14 星期二
 */

class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] res = new int[n];
        res[0] = 1;
        int[] idxs = new int[primes.length];
        for(int i=1; i<n; ++i) {
            int min = Integer.MAX_VALUE;
            for(int j=0; j<primes.length; ++j) {
                int idx = idxs[j];
                min = Math.min(min, res[idx] * primes[j]);
            }
            // 这里是为了去除重复的丑数，比如3*2=6,2*3=6
            for(int j=0; j<primes.length; ++j) {
                int idx = idxs[j];
                if (min == res[idx] * primes[j])
                    idxs[j]++;
            }
            res[i] = min;
        }
        return res[n-1];
    }
}
